# 全排列3
def permuteUnique(nums):
    if not nums:
        return []
    result=[]
    path=[]
    used=[0]*len(nums)
    def backtracking(nums,used):
        if len(path)==len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if not used[i]:
                if i>0 and nums[i]==nums[i-1] and not used[i-1]:
                    continue
                used[i]=1
                path.append(nums[i])
                backtracking(nums,used)
                path.pop()
                used[i]=0
    backtracking(sorted(nums),used)
    return result
lt=permuteUnique([1,1,2])
print(lt)
